The present invention relates to methods and apparatus for multiplying two binary numbers using a Booth multiplier.
Many of the processes performed by information handling systems and the like involve the multiplication of binary numbers. In a multiplication function, there exists a multiplicand and a multiplier. As is well known in the art, binary numbers are multiplied through a process of multiplying the multiplicand by the first bit of the multiplier. Next, the multiplicand is multiplied by the second bit of the multiplier, shifting the result one digit and adding the products. This process is continued until each bit of the multiplier has been multiplied by the multiplicand.
Each of the products produced by multiplying the multiplicand by a bit of the multiplier produces a number which is referred to as a partial product. The resulting product is formed by accumulating the partial products propagating the carries from the rightmost columns to the left. This process is referred to as partial product accumulation. Although this process works well for its intended purpose, it has a significant drawback in that in order to implement this process utilizing hardware, a significant number of logic gates and other circuitry are required. As a result, implementing this process with hardware may be cost prohibitive and may result in very slow processing speeds, especially for large bit numbers.
In order to speed up the process by decreasing the number of partial products generated during the multiplication of the multiplier binary number and the multiplicand binary number, some known multipliers may employ a Booth encoding algorithm or method. In order to reduce the number of partial products, a known Booth encoding algorithm may recode a radix-2 multiplier Y into a radix-4 multiplier Z with an encoded digital set, {−2, −1, 0, 1, 2}, such that the number of partial products may be reduced by one half. Booth multipliers typically employ encoders and selectors. The encoders convert respective groups of radix 2 bits of the multiplier into radix 4 encoded bits. the selectors operate as multiplexers, where each selector receives a respective group of radix 2 bits of the multiplicand and the groups of radix 2 bits of the multiplier are used as selector bits. The aggregate of the outputs from the selectors for a given group of radix 2 bits of the multiplier results in a partial product.
While this algorithm allows for a reduction of the number of partial products using a redundant number system, the encoder and selector circuits of the known Booth multiplier circuits require a significant number of logic gates to carry out their functions. (Some examples of known Booth encoders and selectors will be discussed in more detail herein below.) This can significantly delay signal propagation through the multiplier. There is a need, however, for a new Booth multiplier that enjoys a lower propagation delay as compared with conventional implementations.